/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 19182
 * Date: 2025-10-26
 * Time: 19:35
 */
public class AVLTree {
    static class AVLTreeNode{
        public int val;
        public AVLTreeNode parent;
        public AVLTreeNode left;
        public AVLTreeNode right;
        public int bf;
        public AVLTreeNode(int val){
            this.val = val;
        }
    }
    public AVLTreeNode root;
    public boolean insert(int val){
        AVLTreeNode node = new AVLTreeNode(val);
        if(root == null){
            root = node;
            return true;
        }
        AVLTreeNode parent = null;
        AVLTreeNode cur = root;
        while(cur != null){
            if(cur.val < val){
                parent = cur;
                cur = cur.right;
            }else if(cur.val == val){
                System.out.println("插入节点重复！");
                return false;
            }else{
                parent = cur;
                cur = cur.left;
            }
        }
        if(parent.val < val){
            parent.right = node;
        }else{
            parent.left = node;
        }
        cur = node;
        node.parent = parent;
        while(parent != null){
            if(parent.right == cur){
                parent.bf++;
            }else{
                parent.bf--;
            }
            if(parent.bf == 0){
                break;
            }
            if(parent.bf == 1 || parent.bf == -1){
                cur = parent;
                parent = cur.parent;
            }else if(parent.bf == 2){
                if(cur.bf == 1){
                    RotateLeft(parent);
                }else{
                    RotateRL(parent);
                }
            }else{
                if(cur.bf == -1){
                    RotateRight(parent);
                }else{
                    RotateLR(parent);
                }
            }
        }
        return true;
    }
    public void RotateLeft(AVLTreeNode parent){
        AVLTreeNode subR = parent.right;
        AVLTreeNode subRL = subR.left;

        subR.left = parent;
        parent.right = subRL;
        if(subRL != null){
            subRL.parent = parent;
        }
        AVLTreeNode pParent = parent.parent;
        parent.parent = subR;
        if(root == parent){
            root = subR;
            subR.parent = null;
        }else{
            if(pParent.left == parent){
                pParent.left = subR;
            }else{
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
        subR.bf = parent.bf = 0;
    }
    public void RotateRight(AVLTreeNode parent){
        AVLTreeNode subL = parent.left;
        AVLTreeNode subLR = subL.right;

        subL.right = parent;
        parent.left = subLR;
        if(subLR != null){
            subLR.parent = parent;
        }
        AVLTreeNode pParent = parent.parent;
        parent.parent = subL;
        if(root == parent){
            root = subL;
            subL.parent = null;
        }else{
            if(pParent.left == parent){
                pParent.left = subL;
            }else{
                pParent.right = subL;
            }
            subL.parent = pParent;
        }
        subL.bf = parent.bf = 0;
    }
    public void RotateRL(AVLTreeNode parent){
        AVLTreeNode subR = parent.right;
        AVLTreeNode subRL = subR.left;
        int bf = subRL.bf;
        RotateRight(parent.right);
        RotateLeft(parent);
        if(bf == 1){
            subRL.bf = 0;
            parent.bf = -1;
            subR.bf = 0;
        }else if(bf == 0){
            subRL.bf = 0;
            parent.bf = 0;
            subR.bf = 0;
        }else{
            subRL.bf = 0;
            parent.bf = 0;
            subR.bf = 1;
        }
    }
    public void RotateLR(AVLTreeNode parent){
         AVLTreeNode subL = parent.left;
         AVLTreeNode subLR = subL.right;
         int bf = subLR.bf;
         RotateLeft(parent.left);
         RotateRight(parent);
         if(bf == 1){
             subLR.bf = 0;
             parent.bf = 0;
             subL.bf = -1;
         }else if(bf == 0){
             subLR.bf = 0;
             parent.bf = 0;
             subL.bf = 0;
         }else{
             subLR.bf = 0;
             parent.bf = 1;
             subL.bf = 0;
         }
    }
    public void Inorder(AVLTreeNode root){
        if(root == null){
            return;
        }
        Inorder(root.left);
        System.out.print(root.val + " ");
        Inorder(root.right);
    }
    public int getHeight(AVLTreeNode root){
        if(root == null){
            return 0;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return leftH > rightH ? leftH + 1 : rightH + 1;
    }
    public boolean isBalanced(AVLTreeNode root){
        if(root == null){
            return true;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        if(Math.abs(leftH - rightH) > 1){
            return false;
        }
        return  isBalanced(root.left) && isBalanced(root.right);
    }
}
